#二叉搜索树

#查找元素

#递归法
def searchBST(root, val):
    if not root or root.val == val: 
        return root
    if root.val > val: 
        return self.searchBST(root.left, val)
    if root.val < val: 
        return self.searchBST(root.right, val)

#迭代法
def searchBST(root, val):
    while root:
        if val < root.val: root = root.left
        elif val > root.val: root = root.right
        else: return root
    return None

#检查一个二叉树是否为二叉搜索树

#递归法
def isValidBST(root):
    cur_max = -float('inf')
    def isBST(root): 
        nonlocal cur_max #用于修改外层函数变量
        if not root: 
            return True
        is_left_valid = isBST(root.left)
        if cur_max < root.val: 
            cur_max = root.val
        else: return False
        is_right_valid = isBST(root.right)
        return is_left_valid and is_right_valid
    return isBST(root)

#迭代法
def isValidBST(root):
    stack = []
    cur = root
    pre = None
    while cur or stack:
        if cur:
            stack.append(cur)
            cur = cur.left
        else: # 逐一处理节点
            cur = stack.pop()
            if pre and cur.val <= pre.val:
                return False
            pre = cur 
            cur = cur.right
    return True

#查找二叉搜索树的众数

def findMode(root):
    stack = []
    cur = root
    pre = None
    maxCount, count = 0, 0
    res = []
    while cur or stack:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:  # 逐一处理节点
            cur = stack.pop()
            if pre == None:  # 第一个节点
                count = 1
            elif pre.val == cur.val:
                count += 1
            else:
                count = 1
            if count == maxCount:
                res.append(cur.val)
            if count > maxCount:
                maxCount = count
                res.clear()
                res.append(cur.val)
            pre = cur
            cur = cur.right
    return res 

#最近公共祖先

#递归法
def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'):
    if root.val > p.val and root.val > q.val:
        return self.lowestCommonAncestor(root.left, p, q)
    if root.val < p.val and root.val < q.val:
        return self.lowestCommonAncestor(root.right, p, q)
    return root

#迭代法
def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'):
    while True:
        if root.val > p.val and root.val > q.val:
            root = root.left
        elif root.val < p.val and root.val < q.val:
            root = root.right
        else:
            return root


#插入元素

#递归法 - 有返回值
def insertIntoBST(root, val):
    if not root: return BinaryTree(val)
    if val < root.val: 
        root.left = insertIntoBST(root.left, val)
    if root.val < val:
        root.right = insertIntoBST(root.right, val)
    return root

#递归法 - 无返回值
def insertIntoBST(root, val):
    newNode = BinaryTree(val)
    if not root: return newNode 
    if not root.left and val < root.val:
        root.left = newNode
    if not root.right and val > root.val:
        root.right = newNode 
    if val < root.val:
        insertIntoBST(root.left, val)
    if val > root.val:
        insertIntoBST(root.right, val)

